Sultan Sallehuddin diputerakan pada 30 April 1942, pada zaman pemerintahan paduka nenda baginda, Sultan Abdul Hamid Halim Shah.[3] Bonda baginda, Tengku Asma merupakan puteri kedua Sultan Terengganu, Sultan Sulaiman Badrul Alam Shah. Baginda diputerakan di istana kerabat diraja Kedah, Istana Anak Bukit pada zaman penjajahan British. Baginda diputerakan dengan nama Tunku Mahmud Sallehuddin dan dibesarkan di Istana Anak Bukit.

Tunku Sallehuddin ialah anakanda kesembilan daripada 14 adik-beradik dan paduka putera keenam daripada 7 orang putera.[4] Ayahandanya Almarhum Sultan Badlishah (1894-1958), Sultan Kedah ke-27 dan ibundanya ialah Sultanah Asma binti Almarhum Sultan Sulaiman Badrul Alam Shah (1911-1994) yang merupakan anak perempuan Sultan Terengganu, Sultan Sulaiman Badrul Alam Shah.

Saudara kandungnya ialah Almarhum Tan Sri Tunku Annuar, Tan Sri Tunku Abdul Hamid Thani, Dato' Seri Tunku Hosnah, Dato' Tunku Bisharah, Dato' Tunku Badriatul Jamal, Dato' Kamaliah dan Dato' Hajjah Tunku Nafisah manakala saudara tiri dari ayahanda yang sama ialah Almarhum Tunku Abdul Hamid, Almarhum Tuanku Abdul Halim, Almarhum Tunku Abdul Malik, Almarhum Tunku Mansur, Almarhumah Dato' Seri Tunku Hamidah dan Dato' Seri Tunku Sakinah.

Tunku Sallehuddin mendapat pendidikan awal di Sekolah Melayu Alor Merah dan meneruskan pengajian di Kolej Sultan Abdul Hamid.[5] Baginda berkelulusan pendidikan tinggi daripada College of Military Engineering Poona di India.